// https://leetcode-cn.com/problems/merge-k-sorted-lists/submissions/
// https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

// 法一：维护大小为k的堆
// 类似：https://gitee.com/xuzh1874/OJ/blob/master/Basis/Data%20Structure/%E5%A0%86/kth-largest-in-n-arrays.cpp
struct cmp {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* dummy = new ListNode(-1);
        ListNode* tmp = dummy;
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for (auto& n: lists) {
            q.push(n);
        }
        while (!q.empty()) {
            ListNode* top = q.top();
            q.pop();
            tmp->next = top;
            tmp = tmp->next;
            q.push(top->next);
        }
        return dummy->next;
    }
};

// 法二：归并排序
class Solution {
public:
    ListNode* mergeSort(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* tmp = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tmp->next = l1;
                l1 = l1->next;
            } else {
                tmp->next = l2;
                l2 = l2->next;
            }
            tmp = tmp->next;
        }
        if (l1) tmp->next = l1;
        if (l2) tmp->next = l2;
        return dummy->next;
    }
    ListNode* merge(vector<ListNode*>& lists, int l, int r) {
        if (lists.empty()) return NULL;
        if (l == r) return lists[l]; //返回条件；这样每次都合并为一个链表
        int m = (r - l) / 2 + l;
        ListNode* left = merge(lists, l, m);
        ListNode* right = merge(lists, m + 1, r);
        return mergeSort(left, right);
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};